package leetcode.primary;

public class T41 {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        if (nums[0]<=len && nums[0]>0){
            if (nums[0]!=1){      //交换
                int temp = nums[0];
                nums[0] = nums[temp-1];
                nums[temp-1] = temp;
            }
        }
        for (int i=1;i<len;i++){
            if (nums[i]<=len && nums[i]>0) {
                if (nums[i] != i + 1) {      //交换
                    int temp = nums[i];
                    if (nums[i] != nums[temp - 1]) {
                        nums[i] = nums[temp - 1];
                        nums[temp - 1] = temp;
                        i--;
                    }
                }
            }
        }

        for (int i =0;i<len;i++){
            if (nums[i]!=i+1){
                return i+1;
            }
        }

        return len+1;

    }

    public static void main(String[] args) {
        T41 test = new T41();
        int ans = test.firstMissingPositive(new int[]{7,8,9,11,12});
        System.out.println("ans="+ans);
    }
}
